import heapq
import sys
from typing import List, Tuple, Dict

class Node:


    def __init__(self, vertex: int, path_cost: int, path: List[int]):
        self.vertex = vertex  # 当前顶点
        self.path_cost = path_cost  # 从起点到当前顶点的路径成本
        self.path = path  # 从起点到当前顶点的路径

    def __lt__(self, other):
        # 用于优先队列比较，成本小的优先级高
        return self.path_cost < other.path_cost


class BranchAndBoundShortestPath:


    def __init__(self, graph: Dict[int, List[Tuple[int, int]]]):

        self.graph = graph
        self.n = len(graph)

    def solve(self, start: int, end: int) -> Tuple[int, List[int]]:

        if start not in self.graph or end not in self.graph:
            raise ValueError("起点或终点不在图中")

        # 初始化优先队列（最小堆）
        priority_queue = []

        # 创建起始节点
        start_node = Node(start, 0, [start])
        heapq.heappush(priority_queue, start_node)

        # 记录到每个顶点的最小成本（用于剪枝）
        min_cost = {vertex: float('inf') for vertex in self.graph}
        min_cost[start] = 0

        best_solution = None
        best_cost = float('inf')

        while priority_queue:
            # 取出当前成本最小的节点（分支限界法的核心）
            current_node = heapq.heappop(priority_queue)

            # 如果当前节点已经是终点，更新最优解
            if current_node.vertex == end:
                if current_node.path_cost < best_cost:
                    best_cost = current_node.path_cost
                    best_solution = current_node.path.copy()
                continue

            # 如果当前路径成本已经超过已知最优解，剪枝
            if current_node.path_cost >= best_cost:
                continue

            # 扩展当前节点的所有邻居
            for neighbor, weight in self.graph.get(current_node.vertex, []):
                new_cost = current_node.path_cost + weight

                # 如果找到更优路径，则扩展该分支
                if new_cost < min_cost[neighbor]:
                    min_cost[neighbor] = new_cost
                    new_path = current_node.path + [neighbor]
                    new_node = Node(neighbor, new_cost, new_path)
                    heapq.heappush(priority_queue, new_node)

        if best_solution is None:
            return float('inf'), []

        return best_cost, best_solution

    def solve_all_pairs(self, start: int) -> Dict[int, Tuple[int, List[int]]]:

        results = {}

        for end_vertex in self.graph:
            if end_vertex != start:
                cost, path = self.solve(start, end_vertex)
                results[end_vertex] = (cost, path)

        return results


def print_solution(cost: int, path: List[int]):

    if cost == float('inf'):
        print("没有路径存在")
    else:
        print(f"最短路径长度: {cost}")
        print(f"路径: {' -> '.join(map(str, path))}")


# 测试示例
if __name__ == "__main__":
    # 示例图（有向图）
    graph = {
        0: [(1, 4), (2, 1)],
        1: [(3, 1)],
        2: [(1, 2), (3, 5)],
        3: [(4, 3)],
        4: []
    }

    print("图结构:")
    for vertex, edges in graph.items():
        print(f"顶点 {vertex}: {edges}")
    print()

    solver = BranchAndBoundShortestPath(graph)

    # 测试从顶点0到顶点4的最短路径
    start, end = 0, 4
    print(f"从顶点 {start} 到顶点 {end} 的最短路径:")
    cost, path = solver.solve(start, end)
    print_solution(cost, path)
    print()

    # 测试从顶点0到所有其他顶点的最短路径
    print(f"从顶点 {start} 到所有其他顶点的最短路径:")
    all_paths = solver.solve_all_pairs(start)
    for end_vertex, (cost, path) in all_paths.items():
        print(f"到顶点 {end_vertex}: ", end="")
        print_solution(cost, path)

